package algorithm.middle;

import javax.print.DocFlavor;
import java.util.Arrays;

/**
 * 给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
 * 输出： True
 * 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
 * 示例 2:
 * <p>
 * 输入: nums = [1,2,3,4], k = 3
 * 输出: false
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/partition-to-k-equal-sum-subsets
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class CanPartitionKSubsets698 {

    static int count = 0;


    public static boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if (sum % k != 0) return false;
        Arrays.sort(nums);
        int target = sum / k;
        if (nums[nums.length - 1] > target) return false;
        for (int i = nums.length-1; i > -1; i--) {
            if (nums[i]==0) continue;
            dfs(nums, target, i, i+1);
        }
        return  count == k;
    }

    //target缺乏的数
    public static boolean dfs(int[] nums, int target, int index, int preIndex) {
        if (index<0){
            return false;
        }
        if (nums[index] == target) {
            count++;
            return true;
        }
        if (index > 0) {
            if (nums[index] < target) {
                if (dfs(nums, target - nums[index], index - 1, index)) {
                    nums[index] = 0;
                    return true;
                } else {
                    return dfs(nums, target, index - 1, preIndex);
                }
            } else {
                return dfs(nums, target, index - 1, preIndex);
            }
        }
        return dfs(nums,target,preIndex-2,preIndex-1);
    }

    public static void main(String[] args) {
//        canPartitionKSubsets(new int[]{4, 4, 6, 2, 3, 8, 10, 2, 10, 7}, 4);
//        canPartitionKSubsets(new int[]{4, 3, 2, 3, 5, 2, 1}, 4);
        String format = String.format("Exception raised", "属实");
        System.out.println(format);
        String format2 = String.format("Exception raised %s %s", "属实");
        System.out.println(format2);
    }


    public static int[] numUsed;
    public boolean canPartitionKSubsets2(int[] nums, int k) {
        numUsed = new int[nums.length];
        Arrays.sort(nums);
        int sum = Arrays.stream(nums).sum();
        if (sum % k != 0 || nums[nums.length - 1] > sum / k) return false;
        return divideGroups2(nums, nums.length - 1, sum / k, 0, k);
    }

    public boolean divideGroups2(int[] nums, int start, int target, int current, int k) {
        if (k == 1) return true; // 分组操作执行k-1次之后，最后剩余的元素，就是最后一组了，不需要再匹配
        if (current == target) return divideGroups2(nums, nums.length - 1, target, 0, k - 1); // 分组操作执行k-1次后，最后剩余的元素，就是最后一组了，不需要再匹配
        for (int i = start; i >= 0; i--) {
            if (numUsed[i] == 1 || current + nums[i] > target) continue; // 被使用的元素，不能再次使用；总和大于目标值，也不能使用
            numUsed[i] = 1; // 标记占用
            if (divideGroups2(nums, i - 1, target, current + nums[i], k)) return true;
            numUsed[i] = 0; // 撤销标记
            while (i > 0 && nums[i - 1] == nums[i]) i--; // 例如“12333333...”，假如最右侧的“3”这个值没有匹配上，那么它左侧的剩余五个“3”都不需要再匹配了。
        }
        return false;
    }
}



